1. Field of the Invention
The present subject matter relates generally to random number generation including generation of a random byte stream with uniform statistical properties.
2. Related Art
Random number generation is critically important in many areas. For example, generation of random numbers is a crucial element of maintaining data security. Many different forms of encryption are available to use in conjunction with random number generation. True random number generation can be used to make it practically impossible for an attacker to unscramble digital messages. However, to the extent that the random number generator produces results that are deterministic, vulnerability of encryption increases.
As sophistication of encryption has increased, the sophistication of attackers has steadily increased. Extremely complex encryption systems have been broken. Widely-used existing encryption algorithms such as DES, SSL, and RSA have been broken.
There are many different forms of encryption which each rely on random number generation. The everyday significance of the ability to provide a random number stream is illustrated by a research project reported in the New York Times in 2012, http://www.nytimes.com/2012/02/15/technology/researchers-find-flaw-in-an-online-encryption-method.html?_r=3&hp=&pagewanted=print#. Researchers examined a random number generation system which was a building block of encryption systems used worldwide for online shopping, banking, e-mail, and other Internet services intended to remain private and secure. The researchers discovered that in a small but significant number of cases, the random number generation system failed to work.
In the particular encryption system examined by the researchers, a user first creates and publishes the product of two large prime numbers, in addition to another number, to generate a public “key.” The original numbers are kept secret. To encrypt a message, a second person employs a formula that contains the public key. In practice, only someone with knowledge of the original prime numbers can decode that message. The secret prime numbers must be generated randomly.
The researchers examined public databases of 7.1 million public keys used to secure e-mail messages, online banking transactions, and other secure data exchanges. They used the Euclidean algorithm to find the greatest common divisor of two integers in order to examine public key numbers. They found that approximately 27,000 keys were not truly random and provided essentially no protection against an attacker. An attacker could determine the underlying numbers, or secret keys, used to generate the public key using the same methods as the researchers. Many other keys were weak.
The researchers did not determine why the random number generators had produced imperfect results. However, it was seen that the problem appeared in the work of a number of sophisticated software developers. Widespread vulnerability exists which may go undetected until an adverse event occurs.
A form of random number generator that has come in to wide use is the multiply-with-carry random number generator of George Marsaglia. Journal of Modern Applied Statistical Methods 2(1)2-12 (2003), http://www.jmasm.com/journal/2003_vol2_no1.pdf. Many pseudorandom keys may be generated. However, the generated numbers tend to “band.” The statistical distribution of the byte stream produced is not uniform. Consequently the byte stream is at least to some degree deterministic, creating vulnerability. Post processing of generated values is required to improve statistical properties. An initial byte stream with uniform statistical distribution is not provided.